package liangtWorkSpace.simple;

import java.util.HashMap;

/**
 * @ClassName SoluTion
 * @Description : 求两个数的和与指定数相等
 * @Author : LiangT
 * @Date : 2020/6/11 12:32
 */
public class SoluTion {
    /**
     * 思路1 双层循环获取结果
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] towSum1(int[] nums, int target) {
        int[] index = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (target == nums[i] + nums[j]) {
                    index[0] = i;
                    index[1] = j;
                    return index;
                }
            }
        }
        return index;
    }

    public int[] towSum2(int[] nums, int target) {
        int[] index = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums.length - 1; j > i; j--) {
                if (target == nums[i] + nums[j]) {
                    index[0] = i;
                    index[1] = j;
                    return index;
                }
            }
        }
        return index;
    }

    /**
     * @param nums
     * @param target
     * @return
     */
    public int[] towSum3(int[] nums, int target) {
        int[] index = new int[2];
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (hash.containsKey(nums[i])) {
                index[1] = i;
                index[0] = hash.get(nums[i]);
                return index;
            }
            // 将数据存入 key为补数 ，value为下标
            hash.put(target - nums[i], i);
        }
        return index;
    }

    /**
     * 有序数组求给定值和下标
     * @param numbers
     * @param target
     * @return
     */
    public int[] towSum4(int[] numbers, int target) {
        int[] index = new int[2];
        int start = 0;
        int end = numbers.length-1;
        while (start < end){
            if (numbers[start] + numbers[end] == target){
                break;
            }
            if (numbers[start] + numbers[end] > target){
                end--;
            }else {
                start++;
            }
        }
        index[0] = start+1;
        index[1] = end+1;
        return index;
    }
    public int[] towSum5(int[] numbers, int target) {
        int[] index = new int[2];
        int start = 0;
        int end = numbers.length-1;
        int nim;
        while (start < end){
            if (numbers[start] + numbers[end] == target){
                break;
            }
            nim = end/2;
            if (numbers[start] + numbers[nim] < target){
                start = nim;
            }else{
                end = nim;
            }
        }
        index[0] = start+1;
        index[1] = end+1;
        return index;
    }
}
